๋ฌธ์
๐ Logic
class Trie {
private TrieNode forward;
private TrieNode backward;
...
}
-
ํธ๋ผ์ด๋ฅผ ์ ๋ฐฉํฅ, ๋ท๋ฐฉํฅ์ผ๋ก 2๊ฐ ์์ฑํ๋ค.
- ์ ๋์ฌ๊ฐ ?์ธ ๊ฒฝ์ฐ๋ ํ์ํด์ผ ํ๋ ๊ฒฝ์ฐ๊ฐ ๋ง๊ณ ์ด๋๋ฌธ์ ์๊ฐ ์ด๊ณผ ๋ฐ์ํ๊ธฐ ๋๋ฌธ์ ์ด์ ๊ฐ์ด ๋๋์ด ์์ฑํ๋ค.
- ํธ๋ผ์ด ๊ตฌ์กฐ๋ฅผ ๋๋์ด ์ ์ฅํ๊ธฐ์, ์ ๋์ฌ์ ๋ฐ๋ผ ํ์ํ๋ ํธ๋ผ์ด ๊ตฌ์กฐ๋ฅผ ๋ฐ๊ฟ๊ฐ๋ฉฐ count๋ฅผ ๊ณ์ฐํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class TrieNode {
private Map<Character, TrieNode> childNodes = new HashMap<>();
int count;
// ์์ ๋
ธ๋ ๋งต Getter
public Map<Character, TrieNode> getChildNodes() {
return this.childNodes;
}
}
class Trie {
// ํธ๋ผ์ด๋ฅผ ์ ๋ฐฉํฅ, ๋ท๋ฐฉํฅ์ผ๋ก 2๊ฐ ์์ฑ
// ์ ๋์ฌ๊ฐ ?์ธ ๊ฒฝ์ฐ๋ ํ์ํด์ผ ํ๋ ๊ฒฝ์ฐ๊ฐ ๋ง๊ณ ์ด๋๋ฌธ์ ์๊ฐ ์ด๊ณผ ๋ฐ์...
private TrieNode forward;
private TrieNode backward;
public Trie() {
forward = new TrieNode();
backward = new TrieNode();
}
public void insert(String word) {
insertBackward(word);
insertForward(word);
}
// ์ฃผ์ด์ง ๋ฌธ์์ ๋ท๋ถ๋ถ๋ถํฐ Trie ๊ตฌ์กฐ ์์ฑ, count ๊ณ์ฐ
private void insertBackward(String word) {
TrieNode node = backward;
for (int i = word.length() - 1; i >= 0; i--) {
node.count++;
char ch = word.charAt(i);
Map<Character, TrieNode> childNodes = node.getChildNodes();
childNodes.putIfAbsent(ch, new TrieNode());
node = childNodes.get(ch);
}
}
// ์ฃผ์ด์ง ๋ฌธ์์ ์๋ถ๋ถ๋ถํฐ Trie ๊ตฌ์กฐ ์์ฑ, count ๊ณ์ฐ
private void insertForward(String word) {
TrieNode node = forward;
for (int i = 0; i < word.length(); i++) {
node.count++;
char ch = word.charAt(i);
Map<Character, TrieNode> childNodes = node.getChildNodes();
childNodes.putIfAbsent(ch, new TrieNode());
node = childNodes.get(ch);
}
}
// ์ ๋์ฌ๊ฐ ?๋ผ๋ฉด ๋ท๋ฐฉํฅ Trie๋ก๋ถํฐ count
// ๊ทธ๋ ์ง ์๋ค๋ฉด ์ ๋ฐฉํฅ Trie๋ก๋ถํฐ count
public int getCount(String query) {
return query.charAt(0) == '?' ? getCountBackward(query) : getCountFarward(query);
}
private int getCountBackward(String query) {
TrieNode node = backward;
for (int i = query.length() - 1; i >= 0; i--) {
char ch = query.charAt(i);
if (ch == '?') return node.count;
Map<Character, TrieNode> childNodes = node.getChildNodes();
if (!childNodes.containsKey(ch)) return 0;
node = childNodes.get(ch);
}
return node.count;
}
private int getCountFarward(String query) {
TrieNode node = forward;
for (int i = 0; i < query.length(); i++) {
char ch = query.charAt(i);
if (ch == '?') return node.count;
Map<Character, TrieNode> childNodes = node.getChildNodes();
if (!childNodes.containsKey(ch)) return 0;
node = childNodes.get(ch);
}
return node.count;
}
}
class Solution {
public int[] solution(String[] words, String[] queries) {
// ๋ฌธ์์ด ๊ธธ์ด๋ฅผ ์ธ๋ฑ์ค๋ก ํ๋ Trie ๋ฐฐ์ด ์ ์ธ
Trie[] trie = new Trie[100001];
int[] answer = new int[queries.length];
// ๋ฌธ์์ด ๊ธธ์ด๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ฐฐ์ด ์ด๊ธฐํ ํ, trie ์์ฑ
for (String word : words) {
int len = word.length();
if (trie[len] == null) trie[len] = new Trie();
trie[len].insert(word);
}
// query ๊ธธ์ด์ ํด๋นํ๋ trie ๋ฐฐ์ด ๊ฐ์ด ์๋ค๋ฉด ํด๋นํ๋ ๋ฌธ์๊ฐ ์๋ค๋ ์๋ฏธ,
// ์๋ค๋ฉด ๊ฐ์ count
for (int i = 0; i < queries.length; i++) {
int len = queries[i].length();
if (trie[len] == null) answer[i] = 0;
else answer[i] = trie[len].getCount(queries[i]);
}
return answer;
}
}
โ๏ธ Review
- ์ฒ์์๋ ์ ๊ท์์ ์ด์ฉํด์ผํ๋ ํ์ง๋ง, ํจ์จ์ฑ ํ
์คํธ๊ฐ ์๋ ๊ฒ์ผ๋ก ๋ณด์ ์ด ๋ฐฉ์์ ์๋ ๋ฏ ํ๊ณ , ๊ณง๋ฐ๋ก
Trie๋ฅผ ์ฌ์ฉํด์ผ๊ฒ ๋ค๋ ์๊ฐ์ด ๋ค์๋ค. - ๋ชจ๋ ๋ฌธ์๊ฐ ?์ธ ๊ฒฝ์ฐ์ ๋ํ ์๊ฐ ์ด๊ณผ๋ฅผ ํด๊ฒฐํ์ง ๋ชปํด ํ์ด๋ฅผ ์ฐธ๊ณ ํ๋ค...